package 中等.链表;

import util.ListNode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。
 * 它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
 * 你可以假设除了数字 0 之外，这两个数字都不会以零开头。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/add-two-numbers-ii
 */
public class 两数相加II_445 {

    public static void main(String[] args) {

        // l1 = [7,2,4,3], l2 = [5,6,4]
        ListNode node7 = new ListNode(7);
        ListNode node2 = new ListNode(2);
        ListNode node4 = new ListNode(4);
        ListNode node3 = new ListNode(3);
        node7.next = node2;
        node2.next = node4;
        node4.next = node3;
        ListNode node5 = new ListNode(5);
        ListNode node6 = new ListNode(6);
        ListNode node44 = new ListNode(4);
        node5.next = node6;
        node6.next = node44;
        addTwoNumbers(new ListNode(5), new ListNode(5));

    }

    /**
     * 栈+模拟
     * 先确定低位，才能确定高位
     *
     * @param l1
     * @param l2
     * @return
     */
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Deque<ListNode> stack1 = new ArrayDeque<>();
        Deque<ListNode> stack2 = new ArrayDeque<>();

        while (l1 != null) {
            stack1.addFirst(l1);
            l1 = l1.next;
        }
        while (l2 != null) {
            stack2.addFirst(l2);
            l2 = l2.next;
        }

        ListNode lowNode = null;
        int lowExtraVal = 0;
        // 可能存在 l1[5] l2[5]  -->  [1,0]
        while (!stack1.isEmpty() || !stack2.isEmpty() || lowExtraVal != 0) {
            int curSum = 0;
            if (!stack1.isEmpty()) {
                curSum += stack1.pollFirst().val;
            }
            if (!stack2.isEmpty()) {
                curSum += stack2.pollFirst().val;
            }
            // 当前位和+低一位进的10
            curSum += lowExtraVal;

            ListNode curNode = new ListNode(curSum % 10);
            lowExtraVal = curSum / 10;
            curNode.next = lowNode;
            lowNode = curNode;
        }
        return lowNode;
    }

}
